import time
import numpy as np
import matplotlib.pyplot as plt
from scipy.interpolate import CubicSpline
from concurrent.futures import ProcessPoolExecutor

# 冒泡排序
def bubble_sort(arr, low=None, high=None):
    if low is None:
        low = 0
    if high is None:
        high = len(arr) - 1
    n = high - low + 1
    for i in range(n):
        for j in range(low, high - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

# 优化冒泡排序
def opt_bubble_sort(arr, low=None, high=None):
    if low is None:
        low = 0
    if high is None:
        high = len(arr) - 1
    n = high - low + 1
    for i in range(n):
        swapped = False
        for j in range(low, high - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break

# 选择排序
def select_sort(arr, low=None, high=None):
    if low is None:
        low = 0
    if high is None:
        high = len(arr) - 1
    n = high - low + 1
    for i in range(low, high + 1):
        min_idx = i
        for j in range(i + 1, high + 1):
            if arr[j] < arr[min_idx]:
                min_idx = j
        if min_idx != i:
            arr[i], arr[min_idx] = arr[min_idx], arr[i]

# 插入排序
def insert_sort(arr, low=None, high=None):
    if low is None: low = 0
    if high is None: high = len(arr) - 1
    for i in range(low + 1, high + 1):
        key = arr[i]
        j = i - 1
        while j >= low and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

# 二分查找插入排序
def bin_insert_sort(arr, low=None, high=None):
    if low is None:
        low = 0
    if high is None:
        high = len(arr) - 1
    for i in range(low + 1, high + 1):
        key = arr[i]
        left, right = low, i - 1
        while left <= right:
            mid = (left + right) // 2
            if arr[mid] > key:
                right = mid - 1
            else:
                left = mid + 1
        for j in range(i - 1, left - 1, -1):
            arr[j + 1] = arr[j]
        arr[left] = key

# 堆排序相关函数
def heapify(arr, n, i):
    largest = i
    l, r = 2 * i + 1, 2 * i + 2
    if l < n and arr[i] < arr[l]:
        largest = l
    if r < n and arr[largest] < arr[r]:
        largest = r
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heap_sort(arr, low=None, high=None):
    if low is None: low = 0
    if high is None: high = len(arr) - 1
    n = high - low + 1
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, low + i)
    for i in range(n - 1, 0, -1):
        arr[low + i], arr[low] = arr[low], arr[low + i]
        heapify(arr, i, low)

# 希尔排序
def shell_sort(arr, low=None, high=None, gaps = 3):
    if low is None: low = 0
    if high is None: high = len(arr) - 1
    n = high - low + 1
    gap = n // gaps
    while gap > 0:
        for i in range(gap + low, high + 1):
            temp = arr[i]
            j = i
            while j >= gap + low and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= gaps

# 快速排序相关函数
def partition(arr, start, end):
    pivot = arr[end]
    i = start - 1

    for j in range(start, end):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]

    arr[i + 1], arr[end] = arr[end], arr[i + 1]

    return i + 1

# 快速排序
def quick_sort(arr, start=None, end=None):
    if start is None:
        start = 0
    if end is None:
        end = len(arr) - 1

    if start < end:
        pivot_index = partition(arr, start, end)
        quick_sort(arr, start, pivot_index - 1)
        quick_sort(arr, pivot_index + 1, end)

# 归并排序相关函数
def merge(arr, left, mid, right):
    l_part, r_part = arr[left:mid + 1], arr[mid + 1:right + 1]
    i, j, k = 0, 0, left
    while i < len(l_part) and j < len(r_part):
        if l_part[i] <= r_part[j]:
            arr[k] = l_part[i]
            i += 1
        else:
            arr[k] = r_part[j]
            j += 1
        k += 1
    while i < len(l_part):
        arr[k] = l_part[i]
        i, k = i + 1, k + 1
    while j < len(r_part):
        arr[k] = r_part[j]
        j, k = j + 1, k + 1

# 归并排序
def merge_sort(arr, low=None, high=None):
    if low is None: low = 0
    if high is None: high = len(arr) - 1
    if low < high:
        mid = (low + high) // 2
        merge_sort(arr, low, mid)
        merge_sort(arr, mid + 1, high)
        merge(arr, low, mid, high)



# 测量排序算法运行时间的函数
def measure_sort_time(sort_func, arr):
    try:
        start = time.time()
        sort_func(arr)
        return time.time() - start
    except Exception as e:
        print(f"Sorting error: {e}")
        return None
 
# 并行计算平均用时
def compute_avg_times(sizes, sort_func, rand_arrays, iterations):
    times = np.zeros(len(sizes))
    
    with ProcessPoolExecutor() as executor:
        for i, size in enumerate(sizes):
            total_time = 0
            
            # 显示进度
            if i % 5 == 0:
                progress = ((i + 1) / len(sizes)) ** 3 * 100
                print(f"{sort_func.__name__}: {progress:05.2f}%...")
            
            # 提交并行任务
            tasks = [executor.submit(measure_sort_time, sort_func, arr.copy()) for arr in [rand_arrays[size]] * iterations]
            
            # 收集结果
            for future in tasks:
                try:
                    total_time += future.result() or 0
                except Exception as e:
                    print(f"Error: {e}")
            
            times[i] = total_time / iterations
    
    print(f"{sort_func.__name__}: 100.00%...")
    return times
 
"""
# 非并行计算版本 
def compute_avg_times(sizes, sort_func, rand_arrays, iterations):
    times = np.zeros(len(sizes))
    
    for i, size in enumerate(sizes):
        total_time = 0
        
        # 显示进度
        if i % 5 == 0:
            progress = ((i + 1) / len(sizes)) ** 2 * 100
            print(f"{sort_func.__name__}: {progress:05.2f}%...")
        
        # 顺序执行排序并测量时间
        for _ in range(iterations):
            total_time += measure_sort_time(sort_func, rand_arrays[size].copy())
        
        times[i] = total_time / iterations
    
    print(f"{sort_func.__name__}: 100.00%...")
    return times
"""

# 绘制排序时间图
def plot_sort_times(sizes, times_dict):
    plt.figure(figsize=(10, 6))
    
    for label, times in times_dict.items():
        cs = CubicSpline(sizes, times)
        x_new = np.linspace(sizes[0], sizes[-1], 1000)
        y_smooth = cs(x_new)
        plt.plot(x_new, y_smooth, label=label)
    
    plt.xlabel('Array Size')
    plt.ylabel('Average Time (seconds)')
    plt.legend()
    plt.grid(True)
    plt.xticks(np.linspace(sizes[0], sizes[-1], 10, dtype=int))
    plt.yticks(np.linspace(min(times.min() for times in times_dict.values()), 
                           max(times.max() for times in times_dict.values()), 10))
    plt.show()
 
# 生成随机数组
def generate_arrays(sizes, rand_min, rand_max):
    return {size: np.random.randint(rand_min, rand_max, size=size) for size in sizes}
 
# 计算排序算法评分
def compute_scores(sizes, times_dict):

    def trapezoidal(x, y):
        n = len(x)
        integral = 0.0
        for i in range(1, n):
            h = x[i] - x[i - 1]
            integral += 0.5 * h * (y[i] + y[i - 1])
        return integral

    total_times = {label: trapezoidal(times, sizes) for label, times in times_dict.items()}
    min_total_time = min(total_times.values())
    scores = {label: 100 * (min_total_time / total_time) for label, total_time in total_times.items()}
    return sorted(scores.items(), key=lambda item: item[1], reverse=True)
 
# 比较排序算法
def compare_sorting_algorithms(min_size, max_size, num_divs, sort_funcs, rand_min=0, rand_max=int(1e5), iterations=6):
    sizes = np.linspace(min_size, max_size, num_divs, dtype=int)
    rand_arrays = generate_arrays(sizes, rand_min, rand_max)
    
    times_dict = {}
    start_time = time.time()
    for label, sort_func in sort_funcs.items():
        times_dict[label] = compute_avg_times(sizes, sort_func, rand_arrays, iterations)
    
    scores = compute_scores(sizes, times_dict)
    exec_time = time.time() - start_time
    
    import os
    os.system('cls' if os.name == 'nt' else 'clear')

    print("\n".join(f"{label}: {score:.2f}" for label, score in scores))
    print(f"Executed in {exec_time:.4f} seconds")
    
    plot_sort_times(sizes, times_dict)


def shell_sort2(arr, low=None, high=None):
    shell_sort(arr, low, high, 2)

def shell_sort3(arr, low=None, high=None):
    shell_sort(arr, low, high, 3)

def shell_sort4(arr, low=None, high=None):
    shell_sort(arr, low, high, 4)

def shell_sort5(arr, low=None, high=None):
    shell_sort(arr, low, high, 5)


# 测试函数
def test_slow_sorts():
    slow_sorts = {
        "Bubble": bubble_sort,
        "Opt Bubble": opt_bubble_sort,
        "Selection": select_sort,
        "Insertion": insert_sort,
        "Bin Insert": bin_insert_sort
    }
    # 数据最小长度，最大长度，划分次数，排序函数，最小随机数，最大随机数，重复计算次数（消除随机误差）
    compare_sorting_algorithms(0, int(1e3), 100, slow_sorts, 0, int(5e5), iterations=10)

def test_fast_sorts():
    fast_sorts = {
        "Heap": heap_sort,
        "Shell": shell_sort,
        "Quick": quick_sort,
        "Merge": merge_sort
    }
    # 数据最小长度，最大长度，划分次数，排序函数，最小随机数，最大随机数，重复计算次数（消除随机误差）
    compare_sorting_algorithms(0, int(1e4), 100, fast_sorts, 0, int(5e5), iterations=10)

def test_shell_sort():
    shell_sorts = {
        "Shell 2": shell_sort2,
        "Shell 3": shell_sort3,
        "Shell 4": shell_sort4,
        "Shell 5": shell_sort5,
    }
    # 数据最小长度，最大长度，划分次数，排序函数，最小随机数，最大随机数，重复计算次数（消除随机误差）
    compare_sorting_algorithms(0, int(1e4), 100, shell_sorts, 0, int(5e5), iterations=10)

if __name__ == "__main__":
    #test_slow_sorts()
    test_fast_sorts()
    #test_shell_sort()
